1039D - You Are Given a Tree - CodeForces Solution

#include<iostream>
#include<stdio.h>
#include<math.h>
#define rg register
using namespace std;
const int N=1e5+5;
struct edge{
	int to,next;
}e[N*2];
int head[N],cnt,fa[N];
void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int f[N],ans[N],dfn[N],rev[N],idx;
void dfs(int u){
	dfn[u]=++idx;
	rev[idx]=u;
	for(rg int i=head[u];i;i=e[i].next){
		rg int v=e[i].to;
		if(v==fa[u]) continue;
		fa[v]=u;
		dfs(v);
	}
}
int read(){
	rg int x=0;
	char c=getchar();
	while(c<'0'||c>'9'){
	//	if(c=='-') flag=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
void write(int x){
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int sol(int lim){
	int num=0,i,j,k,u,v,pos,mx1,mx2;
	for(i=idx;i>=1;--i){
		u=rev[i];
		mx1=mx2=0;
		f[u]=0;
		for(j=head[u];j;j=e[j].next){
			v=e[j].to;
			if(v==fa[u]) continue;
			if(f[v]>mx1){
				mx2=mx1,mx1=f[v];
			}
			else mx2=max(mx2,f[v]);
		}
		if(mx1+mx2+1>=lim) num++,f[u]=0;
		else f[u]=mx1+1;
	}
	return num;
}
int main(){
	int i,u,v,n,T,l,r,mid,ed,tmp;
	n=read();
	for(i=1;i<n;++i){
		u=read();v=read();
		add(u,v);add(v,u);
	}
	T=sqrt(n*log2(n));
	ans[1]=n;
	dfs(1);
	for(i=2;i<=T;++i){//对于每个点数，求最大条数
		ans[i]=sol(i);
	}
	for(i=T+1;i<=n;++i){
		tmp=sol(i);//对于每种条数，二分找最大点数
		l=i,r=n,ed=i;
		while(l<=r){
			mid=(l+r)/2;
			if(sol(mid)==tmp){
				l=mid+1;
				ed=mid;
			}
			else r=mid-1;
		}
		for(;i<=ed;++i) ans[i]=tmp;
		i--;//不然就跳了一个 
	}
	for(i=1;i<=n;++i){
		write(ans[i]);
		putchar('\n');
	} 
	return 0;
}
/*
10
4 7
5 1
8 10
3 9
6 2
1 6
6 8
2 4
8 3
*/